//SamXIAO
#include <bits/stdc++.h>
using namespace std;
#define szCNT_OF(x) (sizeof(x) / sizeof(x[0]))
#define MAX_LEN 20  // 1 * 1000 * 1000 + 86

priority_queue<int> l, r;
int a[100085];
// recursive  递归
int cr_v1(int *a, int n) {
   int res = 0;

   if (1 == n)
      return a[0];
   else if (2 == n)
      return a[1];
   else if (3 == n)
      return a[0] + a[1] + a[2];

   res += min(a[0] * 2 + a[n - 1] + a[n - 2], a[0] + a[1] * 2 + a[n - 1]);
   res += cr_v1(a, n - 2);

   return res;
}

// Iteration 递推、迭代
int cr_v2(int *a, int n) {
   int res = 0;

   while (n > 3) {
      res += min(a[0] * 2 + a[n - 1] + a[n - 2], a[0] + a[1] * 2 + a[n - 1]);
      n -= 2;
   }

   if (1 == n)
      res += a[0];
   else if (2 == n)
      res += a[1];
   else if (3 == n)
      res += a[0] + a[1] + a[2];

   return res;
}

void work1() {
   int n, t;
   scanf("%d", &t);
   while (t--) {
      scanf("%d", &n);
      for (int i = 0; i < n; i++) {
         int x;
         scanf("%d", &x);
         a[i] = x;
      }
      sort(a, a + n);
      printf("%d\n", cr_v1(a, n));
   }
}

int main() {
   work1();
   return 0;
}
